''' 二分法 + 动态规划
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。
给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。
注意，时间上出现重叠的 2 份工作不能同时进行。
如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-profit-in-job-scheduling
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
'''解题思路：二分法bisect'''

from typing import List
import math
from bisect import bisect, bisect_left, bisect_right # 二分法 # 运行时间比for循环更快

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(endTime, startTime, profit))  # 按照结束时间排序
        print(jobs)
        f = [0] * (len(jobs) + 1) #因为会涉及到两个相邻元素之间的比较，所以多给一个位置才能方便比较
        print(f)
        for i, (_, st, p) in enumerate(jobs):
            # print(i, (st, p))
            '''
            bisect_right(jobs, (st, math.inf), hi=i) 
            是在jobs这个数组里面从右往左去寻找 一个 满足条件的下标，
            这个条件是jobs[j] > (st, math.inf)
            这个的大小比较的是第一个元素，也就是jobs[j][0] > st
            即寻找出结束时间大于开始时间的 那个jobs成员 所在下标。
            
            math.inf：估计是为了保证只比较第一个元素的大小，
                      比如字符串的对比，第一个元素对比不满足条件就会对比第二个元素，
                      无穷大就能保证只比较起始结束时间
            
            好处：不需要再多些几个 for循环 去比较开始时间与结束时间的大小了
            '''
            # 从中间开始寻找，找到一个endtime刚好等于st的，然后取下一个值的坐标，或者没有等于st的就直接取恰好大于st的endtime值的坐标
            j = bisect_right(jobs, (st, math.inf), hi=i)  # hi=i 表示二分上界为 i（默认为 n）
            # print(j)
            '''
            # 为什么是 j 不是 j+1：上面算的是 > st，-1 后得到 <= st，但由于还要 +1，抵消了
            f[i+1]：当前区域的最大利润
            f[i]：上一次的最大利润
            f[j]: 表示重叠区域的前一个区域的最大利润，即刚好与i不重叠的那个区域的利润，
            f[j] + p：刚好与i不重叠的那个区域的利润与i区域的利润之和            
            '''
            f[i + 1] = max(f[i], f[j] + p)
            print(f)
        return f[-1] #返回最后一个元素

startTime = [1,2,3,4,5]
endTime = [3,3,4,7,9]
profit = [20,20,50,70,100]

s = Solution()
print(s.jobScheduling(startTime, endTime, profit))



'''-----测试-----'''
ls = [1,5,9,9,9,9,13,17]
index1 = bisect(ls, 9)
index2 = bisect_left(ls, 9)
index3 = bisect_right(ls, 9)
print("index1 = {}, index2 = {}, index3 = {}".format(index1, index2, index3))
ls = [(1,2,3),(2,3,4),(3,4,5),(4,1,1)]
index3 = bisect_right(ls, (3,math.inf))
print(index3)




